package org.lyc.dp;

/**
 * 哪种连续字符串更长
 * 前缀和
 * https://leetcode.cn/problems/longer-contiguous-segments-of-ones-than-zeros/description/
 *
 * @author Liu Yicong
 * @date 2024/3/1
 */
public class KCheckZeroOnes {

	static String s1 = "1101";
	static String s2 = "111000";
	static String s3 = "110100010";

	public static void main(String[] args) {
		System.out.println(checkZeroOnesDP(s1));
		System.out.println(checkZeroOnesDP(s2));
		System.out.println(checkZeroOnesDP(s3));
	}

	/**
	 * 动态规划解法
	 */
	public static boolean checkZeroOnesDP(String s) {
		int n = s.length();
		//dp[0][i] 表示以第i个数字结尾且连续的0的个数; dp[1][i] 表示以第i个数字结尾且连续的1的个数;
		int[][] dp = new int[2][n];
		int[] maxLen = new int[2];
		for (int i = 0; i < n; i++) {
			char current = s.charAt(i);
			int currentValue = Character.getNumericValue(current);
			if (i == 0) {
				dp[currentValue][i] = 1;
				maxLen[currentValue] = 1;
			} else {
				if (current == s.charAt(i - 1)) {
					dp[currentValue][i] = dp[currentValue][i - 1] + 1;
				} else {
					dp[currentValue][i] = 1;
				}
				maxLen[0] = Math.max(maxLen[0], dp[0][i]);
				maxLen[1] = Math.max(maxLen[1], dp[1][i]);
			}
		}
		return maxLen[1] > maxLen[0];
	}

	/**
	 * 模拟解法
	 */
	public static boolean checkZeroOnes(String s) {
		int n = s.length();
		int maxLen1 = 0, len1 = 0, maxLen0 = 0, len0 = 0;
		for (int i = 0; i < n; i++) {
			if (i == 0) {
				if (s.charAt(i) == '1') {
					len1 = 1;
					maxLen1 = 1;
				} else {
					len0 = 1;
					maxLen0 = 1;
				}
				continue;
			}
			if (s.charAt(i) == '1') {
				if (s.charAt(i - 1) == '1') {
					len1++;
				} else {
					len1 = 1;
				}
			}
			if (s.charAt(i) == '0') {
				if (s.charAt(i - 1) == '0') {
					len0++;
				} else {
					len0 = 1;
				}
			}
			maxLen1 = Math.max(len1, maxLen1);
			maxLen0 = Math.max(len0, maxLen0);
		}
		return maxLen1 > maxLen0;
	}
}
